package com.sh.链表;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;

/**
 * @Auther: sh
 * @Version 1.0
 * @Description:
 */
public class 回文链表 {
    public static void main(String[] args) {

    }


    public boolean isPalindrome(ListNode head) {

        /**
         * 1、链表： 两种情况   1 1 2 1 1       1 1 2 2 1 1
         * 2、使用快慢指针找到中间值  奇数就是中间   偶数就是中间值的前一个
         * 3、反转后面的一个节点
         * 4、断开现在中间的节点    就有了两个链表
         * 5、要将后面的链表循环来对比，因为如果是奇数的话，前面的链表会多一个元素，这时按前面的链表来循环的话就会npl
         */


        // 1、找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2、反转其中一个
        ListNode fanzhuang = fanzhuang(slow.next);
        slow.next=null;


        while (fanzhuang!=null){
            if (fanzhuang.val!=head.val){
                return false;
            }
            fanzhuang=fanzhuang.next;
            head=head.next;
        }
        // 3、对比
        return true;
    }

    private ListNode fanzhuang(ListNode head) {
        ListNode fast = head;
        ListNode slow = null;
        while (fast!=null){
            ListNode temp = fast.next;
            fast.next = slow;
            slow = fast;
            fast = temp;
        }
        return slow;
    }
}

